package leetcode.f1t100;

/**
 * 给出数组, 代表紧挨着的石柱高度, 计算所有石柱一起可承接多少单位的水
 * https://leetcode.com/problems/trapping-rain-water/
 *
 * @Author lichongxiao
 * @Date 2022/9/27 15:52
 */
public class Q42_TrappingRainWater {
    /**
     * O(n)space O(n)time
     *
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        int length = height.length;
        int[] preMax = new int[length];
        int[] sufMax = new int[length];
        preMax[0] = height[0];
        for (int i = 1; i < length; i++) {
            preMax[i] = Math.max(preMax[i - 1], height[i]);
        }
        sufMax[length - 1] = height[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            sufMax[i] = Math.max(sufMax[i + 1], height[i]);
        }
        int sum = 0;
        int temp;
        for (int i = 0; i < length; i++) {
            temp = Math.min(preMax[i], sufMax[i]);
            sum += height[i] < temp ? temp - height[i] : 0;
        }
        return sum;
    }

    /**
     * O(1)space O(n)time
     *
     * @param height
     * @return
     */
    public static int trap_2(int[] height) {
        int left = 0, right = height.length - 1, leftMax = height[left], rightMax = height[right],sum=0;
        while (left<=right){
            if(leftMax < rightMax) {
                if(height[left] < leftMax){
                    sum+=leftMax - height[left];
                }else{
                    leftMax = height[left];
                }
                left++;
            }else {
                if(height[right] < rightMax){
                    sum+=rightMax - height[right];
                }else{
                    rightMax = height[right];
                }
                right--;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int testN = 1000, testL = 100, testH = 100;
        for (int i = 0; i < testN; i++) {
            int[] arr = new int[testL];
            for (int j = 0; j < testL; j++) {
                arr[j] = (int)Math.random()*100;
            }
            if(trap(arr) != trap_2(arr)){
                System.out.println("fail");
                for (int j = 0; j < testL; j++) {
                    System.out.print(arr[j]+" ");
                }
                System.out.println(trap(arr));
                System.out.println(trap_2(arr));
            }
        }
        System.out.println("success");
    }
}
